package com.huangyi;
import javax.swing.tree.TreeNode;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //二叉树的锯齿形层序遍历
        class Solution {
            public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
                List<List<Integer>> ans = new ArrayList<>();
                if (root == null) return ans;

                Deque<TreeNode> q = new ArrayDeque<>();
                q.offer(root);
                boolean leftToRight = true;

                while (!q.isEmpty()) {
                    int size = q.size();
                    LinkedList<Integer> cur = new LinkedList<>(); // 双端列表，便于头插/尾插

                    for (int i = 0; i < size; i++) {
                        TreeNode node = q.poll();
                        if (leftToRight) cur.addLast(node.val);
                        else cur.addFirst(node.val);

                        if (node.left != null) q.offer(node.left);
                        if (node.right != null) q.offer(node.right);
                    }

                    ans.add(cur);
                    leftToRight = !leftToRight; // 层与层之间交替
                }
                return ans;
            }
        }

        //二叉树最大宽度
        class Solution2 {
            // 小结构体：存节点和其在完全二叉树中的位置编号
            static class P {
                TreeNode node;
                long idx;
                P(TreeNode n, long i) { node = n; idx = i; }
            }

            public int widthOfBinaryTree(TreeNode root) {
                if (root == null) return 0;

                Deque<P> tmp = new ArrayDeque<>();
                tmp.offer(new P(root, 0L));
                int result = 0;

                while (!tmp.isEmpty()) {
                    int size = tmp.size();
                    long base = tmp.peekFirst().idx; // 本层最小编号，做归一化
                    long first = 0, last = 0;

                    for (int i = 0; i < size; i++) {
                        P cur = tmp.pollFirst();
                        TreeNode node = cur.node;
                        long index = cur.idx - base;   // 归一化后，本层从 0 开始

                        if (i == 0) first = index;
                        if (i == size - 1) last = index;

                        // 用归一化后的 index 推孩子的编号，等效且数值更小
                        if (node.left != null)  tmp.offer(new P(node.left,  index * 2 + 1));
                        if (node.right != null) tmp.offer(new P(node.right, index * 2 + 2));
                    }
                    result = Math.max(result, (int)(last - first + 1));
                }
                return result;
            }
        }
    }
}